package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

 示例:

 输入: n = 4, k = 2
 输出:
 [
 [2,4],
 [3,4],
 [2,3],
 [1,2],
 [1,3],
 [1,4],
 ]
 */
public class _77组合 {

    public List<List<Integer>> combine(int n, int k) {
        ArrayList<List<Integer>> ret = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        backTrack(1,n,k,list,ret);
        return ret;
    }

    private void backTrack(int start,int n, int k, ArrayList<Integer> list, ArrayList<List<Integer>> ret) {
        if( k == list.size() ){
            ret.add( new ArrayList<>(list) );
            return; //记得返回
        }

        for (int i = start; i <= n; i++) {
            list.add(i);
            backTrack(i+1,n,k,list,ret); // i+1 ,不是start +1,不然会出现重复的情况
            list.remove(list.size()-1);
        }
    }
}
